package _hash

import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/palindrome-permutation/description/
 * https://michael.blog.csdn.net/article/details/107096561
 *
 * ```
 * 266.回文排列
 * 给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。
 *
 * 示例 1：
 * 输入: "code"
 * 输出: false
 *
 * 示例 2：
 * 输入: "aab"
 * 输出: true
 *
 * 示例 3：
 * 输入: "carerac"
 * 输出: true
 *
 * ```
 */
class leetcode_266 {

    @Test
    fun test_1() {
        val actual = canPermutePalindrome("code")
        val expected = false
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val actual = canPermutePalindrome("aab")
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_3() {
        val actual = canPermutePalindrome("carerac")
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    private fun canPermutePalindrome(s: String): Boolean {
        val hashMap: HashMap<Char, Int> = HashMap()
        for (ch in s) {
            val count = hashMap[ch] ?: 0
            hashMap[ch] = count + 1
        }

        // 奇数个数<=1， 则是能排成回文
        val count: Int = hashMap.count {
            it.value % 2 != 0
        }
        return count <= 1
    }
}